using System;
using System.Runtime.CompilerServices;
using System.Diagnostics;
using System.Collections.Generic;
using System.Text;

//
// * Copyright (c) 2002-2009 "Neo Technology,"
// *     Network Engine for Objects in Lund AB [http://neotechnology.com]
// *
// * This file is part of Neo4j.
// * 
// * Neo4j is free software: you can redistribute it and/or modify
// * it under the terms of the GNU Affero General Public License as
// * published by the Free Software Foundation, either version 3 of the
// * License, or (at your option) any later version.
// * 
// * This program is distributed in the hope that it will be useful,
// * but WITHOUT ANY WARRANTY; without even the implied warranty of
// * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// * GNU Affero General Public License for more details.
// * 
// * You should have received a copy of the GNU Affero General Public License
// * along with this program. If not, see <http://www.gnu.org/licenses/>.
// 
namespace org.neo4j.kernel.impl.transaction
{


	using SystemException = javax.transaction.SystemException;
	using Transaction = javax.transaction.Transaction;
	using TransactionManager = javax.transaction.TransactionManager;

	using ArrayMap = org.neo4j.kernel.impl.util.ArrayMap;

///
/// <summary> * The Resource Allocation Graph manager is used for deadlock detection. It
/// * keeps track of all locked resources and transactions waiting for resources.
/// * When a <seealso cref="RWLock"/> cannot give the lock to a transaction the tx has to
/// * wait and that may lead to a deadlock. So before the tx is put into wait mode
/// * the <seealso cref="RagManager#checkWaitOn"/> method is invoked to check if a wait of
/// * this transaction will lead to a deadlock.
/// * <p>
/// * The <CODE>checkWaitOn</CODE> throws a <seealso cref="DeadlockDetectedException"/> if
/// * a deadlock would occur when the transaction would wait for the resource. That
/// * will guarantee that a deadlock never occurs on a RWLock basis.
/// * <p>
/// * Think of the resource allocation graph as a node space. We have two node
/// * types, resource nodes (R) and tx/process nodes (T). When a transaction
/// * acquires lock on some resource a relationship is added from the resource to
/// * the tx (R->T) and when a transaction waits for a resource a relationship is
/// * added from the tx to the resource (T->R). The only thing we need to do to see
/// * if a deadlock occurs when some transaction waits for a resource is to
/// * traverse node nodespace starting on the resource and see if we can get back
/// * to the tx ( T1 wants to wait on R1 and R1->T2->R2->T3->R8->T1 <==>
/// * deadlock!). </summary>
/// 
	internal class RagManager
	{
	// if a runtime exception is thrown from any method it means that the
	// RWLock class hasn't kept the contract to the RagManager
	// The contract is:
	// o When a transaction gets a lock on a resource and both the readCount and
	// writeCount for that transaction on the resource was 0
	// RagManager.lockAcquired( resource ) must be invoked
	// o When a tx releases a lock on a resource and both the readCount and
	// writeCount for that transaction on the resource goes down to zero
	// RagManager.lockReleased( resource ) must be invoked
	// o After invoke to the checkWaitOn( resource ) method that didn't result
	// in a DeadlockDetectedException the transaction must wait
	// o When the transaction wakes up from waiting on a resource the
	// stopWaitOn( resource ) method must be invoked

		private readonly Map<object, List<Transaction>> resourceMap = new Dictionary<object, List<Transaction>>();

		private readonly ArrayMap<Transaction, object> waitingTxMap = new ArrayMap<Transaction, object>(5, false, true);

		private readonly TransactionManager tm;

		internal RagManager(TransactionManager tm)
		{
			this.tm = tm;
		}

		[MethodImpl(MethodImplOptions.Synchronized)]
		internal virtual void lockAcquired(object resource, Transaction tx)
		{
			List<Transaction> lockingTxList = resourceMap.get(resource);
			if (lockingTxList != null)
			{
				Debug.Assert(!lockingTxList.Contains(tx));
				lockingTxList.Add(tx);
			}
			else
			{
				lockingTxList = new LinkedList<Transaction>();
				lockingTxList.Add(tx);
				resourceMap.put(resource, lockingTxList);
			}
		}

		[MethodImpl(MethodImplOptions.Synchronized)]
		internal virtual void lockReleased(object resource, Transaction tx)
		{
			List<Transaction> lockingTxList = resourceMap.get(resource);
			if (lockingTxList == null)
			{
				throw new LockException(resource + " not found in resource map");
			}

			if (!lockingTxList.Remove(tx))
			{
				throw new LockException(tx + "not found in locking tx list");
			}
			if (lockingTxList.Count == 0)
			{
				resourceMap.Remove(resource);
			}
		}

		[MethodImpl(MethodImplOptions.Synchronized)]
		internal virtual void stopWaitOn(object resource, Transaction tx)
		{
			if (waitingTxMap.Remove(tx) == null)
			{
				throw new LockException(tx + " not waiting on " + resource);
			}
		}

	// after invoke the transaction must wait on the resource
		lock void checkWaitOn(object resource, Transaction tx)
			throws DeadlockDetectedException;
		{
			List<Transaction> lockingTxList = resourceMap.get(resource);
			if (lockingTxList == null)
			{
				throw new LockException("Illegal resource[" + resource + "], not found in map");
			}

			if (waitingTxMap.get(tx) != null)
			{
				throw new LockException(tx + " already waiting for resource");
			}

			List<Transaction>.Enumerator itr = lockingTxList.GetEnumerator();
			List<Transaction> checkedTransactions = new LinkedList<Transaction>();
			Stack<object> graphStack = new Stack<object>();
		// has resource,transaction interleaved
			graphStack.Push(resource);
			while (itr.MoveNext())
			{
				Transaction lockingTx = itr.Current;
			// the if statement bellow is valid because:
			// t1 -> r1 -> t1 (can happened with RW locks) is ok but,
			// t1 -> r1 -> t1&t2 where t2 -> r1 is a deadlock
			// think like this, we have two transactions and one resource
			// o t1 takes read lock on r1
			// o t2 takes read lock on r1
			// o t1 wanna take write lock on r1 but has to wait for t2
			// to release the read lock ( t1->r1->(t1&t2), ok not deadlock yet
			// o t2 wanna take write lock on r1 but has to wait for t1
			// to release read lock....
			// DEADLOCK t1->r1->(t1&t2) and t2->r1->(t1&t2) ===>
			// t1->r1->t2->r1->t1, t2->r1->t1->r1->t2 etc...
			// to allow the first three steps above we check if lockingTx ==
			// waitingTx on first level.
			// because of this special case we have to keep track on the
			// already "checked" tx since it is (now) legal for one type of
			// circular reference to exist (t1->r1->t1) otherwise we may
			// traverse t1->r1->t2->r1->t2->r1->t2... until SOE
			// ... KISS to you too
				if (lockingTx.Equals(tx))
				{
					continue;
				}
				graphStack.Push(tx);
				checkWaitOnRecursive(lockingTx, tx, checkedTransactions, graphStack);
				graphStack.Pop();
			}

		// ok no deadlock, we can wait on resource
			waitingTxMap.put(tx, resource);
		}

		private synchronized void checkWaitOnRecursive(Transaction lockingTx, Transaction waitingTx, List<Transaction> checkedTransactions, Stack<object> graphStack) throws DeadlockDetectedException
		{
			if (lockingTx.Equals(waitingTx))
			{
				StringBuilder circle = null;
				object resource = null;
				do
				{
					lockingTx = (Transaction) graphStack.Pop();
					resource = graphStack.Pop();
					if (circle == null)
					{
						circle = new StringBuilder();
						circle.Append(lockingTx + " <- " + resource);
					}
					else
					{
						circle.Append(" <- " + lockingTx + " <- " + resource);
					}
				}
				while (!graphStack.isEmpty());
				throw new DeadlockDetectedException(waitingTx + " can't wait on resource " + resource + " since => " + circle);
			}
			checkedTransactions.Add(lockingTx);
			object resource = waitingTxMap.get(lockingTx);
			if (resource != null)
			{
				graphStack.Push(resource);
			// if the resource doesn't exist in resorceMap that means all the
			// locks on the resource has been released
			// it is possible when this tx was in RWLock.acquire and
			// saw it had to wait for the lock the scheduler changes to some
			// other tx that will release the locks on the resource and
			// remove it from the map
			// this is ok since current tx or any other tx will wake
			// in the synchronized block and will be forced to do the deadlock
			// check once more if lock cannot be acquired
				List<Transaction> lockingTxList = resourceMap.get(resource);
				if (lockingTxList != null)
				{
					List<Transaction>.Enumerator itr = lockingTxList.GetEnumerator();
					while (itr.MoveNext())
					{
						lockingTx = itr.Current;
					// so we don't
						if (!checkedTransactions.Contains(lockingTx))
						{
							graphStack.Push(lockingTx);
							checkWaitOnRecursive(lockingTx, waitingTx, checkedTransactions, graphStack);
							graphStack.Pop();
						}
					}
				}
				graphStack.Pop();
			}
		}

		lock void dumpStack()
		{
			Console.Write("Waiting list: ");
			IEnumerator <Transaction> transactions = waitingTxMap.Keys.GetEnumerator();
			if (!transactions.MoveNext())
			{
				Console.WriteLine("No transactions waiting on resources");
			}
			else
			{
				Console.WriteLine();
			}
			while (transactions.MoveNext())
			{
				Transaction tx = transactions.Current;
				Console.WriteLine("" + tx + "->" + waitingTxMap.get(tx));
			}
			Console.Write("Resource lock list: ");
//JAVA TO VB & C# CONVERTER TODO TASK: Java wildcard generics are not converted to .NET:
//ORIGINAL LINE: IEnumerator <?> resources = resourceMap.keySet().iterator();
			IEnumerator <?> resources = resourceMap.Keys.GetEnumerator();
			if (!resources.MoveNext())
			{
				Console.WriteLine("No locked resources found");
			}
			else
			{
				Console.WriteLine();
			}
			while (resources.MoveNext())
			{
				object resource = resources.Current;
				Console.Write("" + resource + "->");
				IEnumerator <Transaction> itr = resourceMap.get(resource).GetEnumerator();
				if (!itr.MoveNext())
				{
					Console.WriteLine(" Error empty list found");
				}
				while (itr.MoveNext())
				{
					Console.Write("" + itr.Current);
					if (itr.MoveNext())
					{
						Console.Write(",");
					}
					else
					{
						Console.WriteLine();
					}
				}
			}
		}

		Transaction getCurrentTransaction()
		{
			try
			{
				return tm.getTransaction();
			}
			catch (SystemException e)
			{
				throw new TransactionFailureException("Could not get current transaction.", e);
			}
		}
	}
}